package com.ting.test.algorithms.递归和动态规划.从左往右的模型;

/**
 * 给定一个正数n，求n的裂开方法数，
 * 规定：后面的数不能比前面的数小
 * 比如4的裂开方法有：
 * 1+1+1+1、1+1+2、1+3、2+2、4
 * 5种，所以返回5
 */
public class N裂开的方法数 {
    public static void main(String[] args) {
        int n = 5;
        int ways = ways(5);
    }

    private static int ways(int n) {
        if (n == 1) {
            return 1;
        }
        return process(1, n);
    }

    /**
     * 该方法返回的是以model为模，分裂rest的方法数
     *
     * @param model 表示当前分裂的模
     * @param rest  表示还剩下未分裂的数
     * @return
     */
    private static int process(int model, int rest) {

        if (rest == 0) {
            //表示正好被分配完
            return 1;
        }
        //注意 这种情况实际上已经被包含在下面的for循环中了
//        if (rest == model) {
//            //如果rest==model 则表明已经分裂完了，并且是有效的
//            return 1;
//        }
        if (rest < model) {
            return 0;
        }

        int ways = 0;
        for (int i = model; i <= rest; i++) {
            ways += process(i, rest - i);
        }
        return ways;
    }


    /**
     * 该方法返回的是以model为模，分裂rest的方法数
     *
     * @param model 表示当前分裂的模
     * @param rest  表示还剩下未分裂的数
     * @return
     */
    private static int dp(int model, int rest) {
        int[][] dp = new int[rest + 1][model + 1];
        dp[0][0] = 1;

        int ways = 0;
        for (int i = model; i <= rest; i++) {
            ways += process(i, rest - i);
        }
        return ways;
    }
}
